#pragma once
#include <iostream>

#define MAXSIZE 100

using namespace std;

template<class T>
class queue
{
public:
    T data[MAXSIZE];
    int front, rear;
};

/*
 * 邻接矩阵
 */
// 基于邻接矩阵存储结构的图的类实现
template<class T>
class MGraph
{
public:
    MGraph(T a[], int n, int e);// 构造函数建立具有N个定点e条边的图
    ~MGraph(){}// 析构函数
    void DFSTraaverse(int v);// 深度优先遍历图
    void BFSTraverse(int v);// 广度优先遍历图
    void listVertexes();//列出全部节点
    void listEdges();//列出全部边
private:
    T vertex[MAXSIZE];// 存放图中顶点的数组
    int edge[MAXSIZE][MAXSIZE];// 存放图中边的数组
    int vertexNum, edgeNum;// 图中顶点数和边数
};    
    //成员函数
    //构造函数建立具有n个定点e条边的图
template <typename T>    
MGraph<T>::MGraph(T a[], int n, int e){
    	cout << "请输入边的端点和权重:" << endl;
	vertexNum = n;
    	edgeNum = e;
    	for (int i = 0; i < vertexNum; i++){ // 顶点初始化
        	vertex[i] = a[i];
	}
    	for (int i = 0; i < vertexNum; i++){ // 邻接矩阵初始化
        	for (int j = 0; j < vertexNum; j++){
            		edge[i][j] = 0;
		}
	}
        for (int k = 0; k < edgeNum; k++){
        int u, v, w;
        cin >> u >> v >> w;        // 输入边依附的顶点的编号和该边的权重
        edge[u][v] = w;            // 置有边标记
        }
    }
	
    //深度优先遍历图
template <typename T>	
void MGraph<T>::DFSTraaverse(int v){
    	cout << vertex[v]<<" ";
        int visit[MAXSIZE] = { 0 };// 顶点是否被访问的标记
	visit[v] = 1;
    	for (int j = 0; j < vertexNum; j++){
        	if (edge[v][j] == 1 && visit[j] == 0)
            	DFSTraaverse(j);
    	}
    }

//广度优先遍历图
template <typename T>
void MGraph<T>::BFSTraverse(int v){
    	queue<T> Q;
    	Q.front = Q.rear = -1;    // 初始化队列
    	cout << vertex[v]<<" ";
    	int visited[MAXSIZE] = {0};
	visited[v] = 1;
        Q.data[++Q.rear] = v;    // 被访问顶点入队
    	while (Q.front != Q.rear){
        	v = Q.data[++Q.front];    // 对头元素出队
        	for (int j = 0; j < vertexNum; j++){
            		if (edge[v][j] == 1 && visited[j] == 0){
                		std::cout << vertex[j]<<" ";
                		visited[j] = 1;
                		Q.data[++Q.rear] = j;    // 邻接点入队
            		}
        	}
    	}	
    }

//列出全部节点
template <typename T>
void MGraph<T>::listVertexes(){
	cout << "以邻接矩阵形式存储:" << endl;
	for (int i = 0; i < vertexNum; i++){ 
                cout << vertex[i] << " ";
        }
	cout << endl;
}

template <typename T>
void MGraph<T>::listEdges(){
	int n = 0;
	while ( n < edgeNum){
		for ( int u = 0; u < vertexNum; u++){
			for ( int v = 0; v < vertexNum; v++){
				if(edge[u][v] != 0){
					cout << "(" << u << "," << v << "," << edge[u][v] << ")" << " ";
					n ++;
				}
			}
		}
	}
	cout << endl;
}

/*
 * 邻接表
 */
// 定义边表结点
struct EdgeNode
{
    int adjvex;// 邻接点域
    int weight;// 该边权重
    EdgeNode* next;
};
// 定义顶点表结点
struct VertexNode
{
    int vertex;
    EdgeNode* firstedge;
};

// 基于邻接表存储结构的图的类实现
template<class T>
class ALGraph
{
public:
    ALGraph(T a[], int n, int e);// 构造函数建立具有N个定点e条边的图
    ~ALGraph() {}// 析构函数
    void DFSTraaverse(int v);// 深度优先遍历图
    void BFSTraverse(int v);// 广度优先遍历图
    void listVertexes();//列出全部节点
    void listEdges();//列出全部边
private:
    VertexNode adjlist[MAXSIZE];// 存放顶点的数组
    int vertexNum, edgeNum;// 图中顶点数和边数
};

template<class T>
ALGraph<T>::ALGraph(T a[], int n, int e)
{
    cout << "请输入边的端点和权重:" << endl;
    vertexNum = n;
    edgeNum = e;
    for (int i = 0; i <vertexNum; i++){
        adjlist[i].vertex = a[i];
        adjlist[i].firstedge = nullptr;
    }
    for (int k = 0; k < edgeNum; k++){
        int u, v, w;
        cin >> u >> v >> w;
        EdgeNode* s = new EdgeNode;
        s->adjvex = v;
	s->weight = w; 
        s->next = adjlist[u].firstedge;
        adjlist[u].firstedge = s;
    }
}

template<class T>
void ALGraph<T>::DFSTraaverse(int v)
{
    cout << adjlist[v].vertex;
    int visit[MAXSIZE] = {0};
    visit[v] = 1;
    EdgeNode* p = adjlist[v].firstedge;
    while (p != NULL)
    {
        int j = p->adjvex;
        if (visit[j] == 0)
            DFSTraaverse(j);
        p = p->next;
    }
}

template<class T>
void ALGraph<T>::BFSTraverse(int v)
{
    int visited[MAXSIZE] = { 0 };// 顶点是否被访问的标记
    queue<T> Q;
    Q.front = Q.rear = -1;    // 初始化队列
    cout << adjlist[v].vertex;
    visited[v] = 1;
    Q.data[++Q.rear] = v;// 被访问顶点入队
    while (Q.front != Q.rear)
    {
        v = Q.data[++Q.front];    // 对头元素出队
        EdgeNode* p = adjlist[v].firstedge;
        while (p != NULL)
        {
            int j = p->adjvex;
            if (visited[j] == 0)
            {
                cout << adjlist[j].vertex;
                visited[j] = 1;
                Q.data[++Q.rear] = j;
            }
            p = p->next;
        }
    }
}

template <typename T>
void ALGraph<T>::listVertexes(){
	cout << "以邻接表形式存储:" << endl;
        for (int i = 0; i < vertexNum; i++){
                cout << adjlist[i].vertex << " ";
        }
        cout << endl;
}

template<class T>
void ALGraph<T>::listEdges(){
	for(int u = 0; u < vertexNum; u ++){
		if(adjlist[u].firstedge != nullptr){
			   for(EdgeNode* p = adjlist[u].firstedge; p != nullptr; p = p -> next){ 
			   	int v = p -> adjvex;
			   	int w = p -> weight;
			   	cout << "(" << u << "," << v << "," << w << ")";
			   }
		}
	}
	cout << endl;

}


